package com.matrix.math;


import java.util.ArrayList;
/**
 * Matrix
 * The object that holds the matrix and computes the operations on them
 * @author McGarvie
 *
 */
public class Matrix implements MathObject
{
	/**
	 * Instance Variables
	 */
	private String TAG = "Matrix";
	private String name= "";
	private int index;
	private double[][] matrix;		 //two dimensional array making up the matrix
	
	// Overridden Constructor TO BE USED IN PARSER
	public Matrix(int rows, int cols)
	{
		this.matrix = new double[rows][cols];
	}
	
	/**
	 * Constructor for the Matrix class
	 * @param n the name of the matrix
	 * @param m the string representation of the matrix
	 */
	public Matrix(String n, double[][] m) 
	{
		name = n;
		matrix = m;
	}
	public Matrix clone()
	{
		return new Matrix("", getMatrix());
	}
	/**
	 * gets the double[][] version of the matrix
	 * @return
	 */
	private double[][] getMatrix()
	{
		double[][] temp = new double[numRows()][numCols()];
		for(int i=0; i< temp.length;i++)
		{
			for(int j=0; j<temp[0].length; j++)
			{
				temp[i][j] = matrix[i][j];
			}
		}
		return temp;
	}
	
	/**
	 * 
	 * @param data
	 * @throws Exception 
	 */
	public void setMatrix(double[][] data) throws Exception
	{
		this.matrix = new double[data.length][data[0].length];
		for(int i = 0; i < numRows(); ++i)
			for(int j = 0; j < numCols(); ++j)
				setValueAt(i, j, data[i][j]);
	}

	/**
	 * gets the number of rows in the matrix
	 * @return
	 */
	public int numRows()
	{
		return matrix.length;
	}
	
	/**
	 * gets the number of columns in the matrix
	 * @return
	 */
	public int numCols()
	{
		return matrix[0].length;
	}
	
	/**
	 * gets the value of the matrix at a certain point
	 * @param row
	 * @param col
	 * @return
	 * @throws Exception 
	 */
	public double getValueAt(int row, int col) throws Exception
	{
		if(row >=0 && col>=0 && row<numRows() && col<numCols())
		{
			return matrix[row][col];
		}
		throw new Exception("Out of bounds Exception");
	}
	
	/**
	 * sets the value of the matrix at a certain point
	 * @param row
	 * @param col
	 * @return
	 * @throws Exception 
	 */
	public void setValueAt(int i, int j, double value) throws Exception
	{
		if(i >=0 && j >=0 && i <numRows() && j <numCols())
		{
			this.matrix[i][j] = value;
		}
		else
		{
			throw new Exception("Out of bounds Exception");
		}
	}
	
	/**
	 * Checks the equality of this and another matrix
	 * @param m the other matrix
	 * @return
	 * @throws Exception
	 */
	public boolean equals(Matrix m) throws Exception
	{
		if(m.numRows() != numRows() || m.numCols() != numCols())
		{
			return false;
		}
		for(int i=0; i<numRows(); i++)
		{
			for(int j=0; j<numCols(); j++)
			{
				if(getValueAt(i,j) != m.getValueAt(i, j))
				{
					return false;
				}
			}
		}
		return true;
	}
	/**
	 * Prints the matrix
	 */
	public void print()
	{
		double[][] a = getMatrix();
		for(int i=0; i<a.length; i++)
		{
			for(int j=0; j<a[0].length; j++)
			{
				System.out.print(a[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	/**
	 * returns the name of the matrix
	 * @return
	 */
	public String getName()
	{
		return name;
	}
	
	/**
	 * sets the Name of the Matrix
	 * @param s
	 */
	public void setName(String s)
	{
		name = s;
	}
	/**
	 * Gets the determinant of the matrix
	 * @return
	 * @throws Exception
	 */
	public double determinant() throws Exception
	{
		//if not nxn then the det = 0;
		if(numRows() != numCols())
		{
			return 0;
		}
		//does the plu factorization and gets the p and u matrices
		double[][][] plu = pluFactorizationHelper();
		double[][] p = plu[0];
		double[][] u = plu[2];
		//gets number of row exchanges in the p matrix
		int count =0;
		for(int i=0; i< p.length; i++)
		{
			if(p[i][i] != 1)
			{
				int j =0;
				for(j=i+1; j<p.length; j++)
				{
					if(u[j][i]!=0)
					{
						break;
					}
				}
				if(j== p.length)
				{
					j--;
				}
				p = swapRows(p, i, j);
				count++;
			}
		}
		//computes the determinant of the u matrix
		double det = 1;
		for(int i=0; i<u.length; i++)
		{
			det *= u[i][i];
			if(Double.isInfinite(det))
			{
				throw new Exception("Value Overflow the numbers are Larger than the Calculator can Handle");
			}
		}
		//det of u times the det of the p which is (-1)^number of row exchanges
		return det*Math.pow(-1, count);
	}
	
	/**
	 * Multiplies two matrices 
	 * @param a
	 * @param b
	 * @return
	 * @throws Exception
	 */
	public Matrix multMatrix(Matrix b) throws Exception
	{
		if (numRows() == 0)
		{
			throw new Exception("The length of matrix A's rows is 0");
		}
		if (numCols() != b.numRows())
		{
			throw new Exception("The number of columns of "+getName()+" needs to be the same as the number of rows of "+b.getName());
		}
		
		int n = numCols();
		int m = numRows();
		int p = b.numCols();
		
		double ans[][] = new double[m][p];
    
		for (int i = 0; i < m; i++)
			for (int j = 0; j < p; j++)
				for (int k = 0; k < n; k++)
					ans[i][j] += getValueAt(i, k) * b.getValueAt(k,j);
    
		return new Matrix(getName()+"*"+b.getName(), ans);
	}
	
	/**
	 * adds this Matrix and another Matrix together
	 * @param array1
	 * @return
	 * @throws Exception
	 */
	public Matrix add( Matrix array1) throws Exception
	{
		//integer values to hold the lengths of the arrays. 
		int l= numRows();
		int m= array1.numRows();
		int n = numCols();
		
		//matrix to hold the result.    
		double result [][] = new double [l][n];
		      
		//adds elements from both matrices together.
		for(int i = 0; i < l; i++)
		{
			for(int j = 0; j < n; j++)
			{ 
				result[i][j] = getValueAt(i,j) + array1.getValueAt(i, j);
			}
		}
		return new Matrix(getName()+"+"+array1.getName(), result);
	}
	
	/**
	 * Subtracts the other Matrix from this one
	 * @param array1
	 * @return
	 * @throws Exception
	 */
	public Matrix subtract( Matrix array1) throws Exception
	{
		//integer values to hold the lengths of the arrays.
		int l= numRows();
		int m= array1.numRows();
		int n = numCols();
		
		//matrix to hold the result.
		double result [][] = new double [l][n];
		
		//subtracts array1 from array.
		for(int i = 0; i < l; i++)
		{
			for(int j = 0; j < n; j++)
			{ 
				result[i][j] = getValueAt(i,j) - array1.getValueAt(i, j);
			}
		}
		return new Matrix(getName()+"-"+array1.getName(), result);
	}
	
	/**
	 * transpose()
	 * Returns the transpose of the matrix A
	 * @param 2D array of doubles.
	 * @return 2D array of doubles representing the transpose matrix of a.
	 * @throws Exception 
	 */
	public Matrix transpose() throws Exception
	{
		// a.length represents the rows
		// a[0].length represents the columns
		
		double[][] returnValue = new double[numCols()][numRows()];
		for (int i = 0; i < numRows(); i++)
			for (int j = 0; j < numCols(); j++)
				returnValue[j][i] = getValueAt(i, j);
		return new Matrix(getName()+"T", returnValue);
	}
	
	/**
	 * swaps two rows of matrix a
	 * return double[][]
	 * @throws Exception 
	 */
	private double[][] swapRows(double[][] a, int row1, int row2) throws Exception
	{
		int n = a.length;
		
		if (row1 >= n)
		{
			throw new Exception("row1 is greater than the number of rows");
		}
		if (row2 >= n)
		{
			throw new Exception("row2 is greater than the number of rows "+n);
		}
		
  	     double[] temp = a[row1];
  	     a[row1] = a[row2];
  	     a[row2] = temp;
       
  	     return a;
	}
       

	/**
	 * finds the inverse of matrix a
	 * return double[][]
	 * @throws Exception 
	 */
	public Matrix inverse() throws Exception
	{
		double[][] a = getMatrix();
		int n = a.length;
		int m = a[0].length;
	   
		// checks if the matrix is square, returns null if not
		if (n != m)
		{
			throw new Exception("Matrix not inversable needs to be nxn");
		}
		
		double d = determinant();
		
		// checks if the determinant is zero, returns null if so
		if (d ==0)
		{
			throw new Exception("the determinant of the matrix is zero");
		}
	   
		// finds the inverse of a 2x2 matrix
		if (n == 2)
		{
			double[][] temp = new double[2][2];
		   
			temp[0][0] = a[1][1];
			temp[1][0] = a[1][0] * -1;
			temp[0][1] = a[0][1] * -1;
			temp[1][1] = a[0][0];
			Matrix t1 = new Matrix("temp", temp);
			t1 = t1.multByConstant((1/d));
			t1.setName("inv"+getName());
			return t1;
		}
         
		// finds the inverse of an nxn matrix
		else
		{
			Matrix temp;
			Matrix mm = null;
			mm = adjoint(a);
		  
			//finds 1 divided by the determinant
			double det = 1 / d;
		   
			temp = mm.multByConstant(det);
			temp.setName("inv"+getName());
			return temp;
             
		}
	}
   
	/**
	 * finds the adjoint of the matrix a
	 * returns double[][]
	 */
	public Matrix adjoint(double[][] a) throws Exception
	{
		int n = a.length;
		
		double[][] temp = new double[n][n];
                 
		int ii, jj, ia, ja;
		double d;
                 
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				ia = ja = 0;
                     
				double[][] ap = new double[n-1][n-1];
			   
				for (ii = 0; ii < n; ii++)
				{
					for (jj = 0; jj < n; jj++)
					{
						if ((ii != i) && (jj != j))
						{
							ap[ia][ja] = a[ii][jj];
							ja++;
						}
					}
                       
					if ((ii != i) && (jj != j)) ia++;
                       
					ja = 0;
				}
				Matrix t1 = new Matrix("temp", ap);
				d = t1.determinant();
				temp[i][j] = (double) Math.pow(-1,i + j) * d;
			}
		}
		Matrix t1 = new Matrix("temp", temp);
		t1 = t1.transpose();
	   
		return t1;
	}
	
	/**
	 * gets the P-L-U factorization of this matrix
	 * @return
	 * @throws Exception 
	 */
	private double[][][] pluFactorizationHelper() throws Exception
	{
		//check the number of columns
		if(numRows() != numCols())
		{
			throw new Exception("Needs to be a square matrix");
		}
		//creates the p l and u matrices 
		double[][] u = getMatrix();
		double[][] l = new double[u.length][u.length];
		double[][] p = new double[u.length][u.length];
		//sets p equal to identity matrix
		for(int i=0; i<u.length; i++)
		{
			p[i][i] = 1;
		}
		//performing all the row operations 
		for(int i=0; i<u.length-1; i++)
		{
			int k =i;
			//while the element of the matrix is 0 then go to the next element in the matrix
			while(k<u[0].length-1 && u[i][k] == 0)
			{
				//tries to find a row that does not have 0 for the kth element
				if(u[i][k] == 0)
				{
					int j =0;
					for(j=k+1; j<u.length; j++)
					{
						if(u[j][k]!=0)
						{
							u = swapRows(u, i, j);
							p = swapRows(p, i, j);
							l = swapRows(l, i, j);
							break;
						}
						if(j+1 == u.length)
						{
							break;
						}
					}
					
				}
				//if no row exists go to the next element
				if(u[i][k] == 0)
				{
					k++;
				}
			}
			//if not 0 then set l matrix element and subtract the jth row from the ith row
			if(u[i][k] != 0)
			{
				for(int j=i+1; j<u.length; j++)
				{
					l[j][k] = u[j][k]/u[i][k];
					u = this.subtractRows(u, i, j, u[i][k], u[j][k]);	
				}
			}
			
		}
		//finds an shifts the 0 rows to the bottom of the matrix
		for(int i=0; i<u.length-1; i++)
		{
			int zeroRow = 0;
			int j =0;
			for(j=0; j<u[0].length; j++)
			{
				if(u[i][j] == 0)
				{
					zeroRow++;
				}
			}
			if(zeroRow == u[0].length)
			{
				int k =0;
				for(j=i+1; j<u.length; j++)
				{
					zeroRow = 0;
					for(k=0; k<u[0].length; k++)
					{
						if(u[j][k] == 0)
						{
							zeroRow++;
						}
					}
					if(zeroRow < u[0].length)
					{
						break;
					}
				}
				if(zeroRow<u[0].length)
				{
					u = swapRows(u, i, j);
					p = swapRows(p, i, j);
					l = swapRows(l, i, j);
				}
				
			}
			
		}
		//sets the diagonal of the l matrix to 1's 
		for(int i=0; i<u.length; i++)
		{
			l[i][i] = 1;
			//System.out.print(p[u.length-1][i]);
		}
		//puts the three matrices into the return value
		double[][][] retVal = new double[3][][];
		retVal[0] = p;
		retVal[1] = l;
		retVal[2] = u;
		return retVal;
	}
	/**
	 * puts the plu factorization into Matrix objects
	 * @return
	 * @throws Exception
	 */
	public ArrayList<Matrix> pluFactorization() throws Exception
	{
		double[][][] plu = pluFactorizationHelper();
		ArrayList<Matrix> mlist = new ArrayList<Matrix>();
		mlist.add(new Matrix("P", plu[0]));
		mlist.add(new Matrix("L", plu[1]));
		mlist.add(new Matrix("U", plu[2]));
		return mlist;
	}
	
	/**
	 * Solves for the x Vector 
	 * @param b
	 * @return
	 */
	public ArrayList<ColumnVector> axbSolve(ColumnVector b) throws Exception
	{
		if(b.length() != numRows())
		{
			throw new Exception("The vector must have the same length as the matrices number of Rows.");
		}
		ArrayList<ColumnVector> results = new ArrayList<ColumnVector>();
		ArrayList<Matrix> plu = null;
		
		double[][][] reduce = reduce(b);
		double[][] u = reduce[0];
		double[] v = reduce[1][0];
		Matrix m = new Matrix("Reduced", u);
		ColumnVector vector = new ColumnVector("reduce", v);
		ColumnVector result = m.solveUpperTriang(vector);
		if(determinant()!=0)
		{
			results.add(result);
		}
		else
		{
			results.add(result);
			results.addAll(nullSpace());
		}
		
		return results;
	}
	
	private ColumnVector solveUpperTriang(ColumnVector v) throws Exception
	{
		//back subs through the upper triangular matrix
		//if contains free variables they will all be equal to zero
		double[] result = new double[numCols()];
		for(int i=numRows()-1; i>=0; i--)
		{
			int k =i;
			
			while(k<numCols() && getValueAt(i,k) == 0)
			{
				k++;
			}
			if(k!=numCols())
			{
				result[k] = v.getValueAt(i);
				for(int j=k+1; j<numCols(); j++)
				{
					result[k] -= getValueAt(i, j)*result[j]; 
				}
				result[k] /= getValueAt(i,k);
			}
			else if(v.getValueAt(i)!= 0)
			{
				//if an entire row is equal to 0 and the corresponding vector element
				//is not 0 then there are no solutions
				throw new Exception("There are no solutions");
			}
		}
		return new ColumnVector("U solve", result);
	}
	/**
	 * Multiplies the Matrix by a column vector
	 * @param v
	 * @return
	 * @throws Exception
	 */
	public ColumnVector multByVector(ColumnVector v) throws Exception
	{
		if(v.length() != numCols())
		{
			throw new Exception("The vector must have the same length as the matrices number of columns.");
		}
		double[] result = new double[numRows()];
		for(int i=0; i<numRows(); i++)
		{
			for(int j=0; j < numCols(); j++)
			{
				result[i] += getValueAt(i,j)*v.getValueAt(j);
			}
		}
		return new ColumnVector(getName()+"*"+v.getName(), result);
	}
	
	/**
	 * multiplies this matrix by a constant
	 * @param c
	 * @return
	 * @throws Exception 
	 */
	public Matrix multByConstant(double c) throws Exception
	{
		double temp[][] = new double[numRows()][numCols()];
   
		for (int i = 0; i < numRows(); i++)
			for (int j = 0; j < numCols(); j++)
			{
				temp[i][j] = this.getValueAt(i, j) * c;
			}
		
		return new Matrix("c*"+getName(), temp);
	}
	
	/**
	 * gets the nullspace of this matrix
	 * @return
	 * @throws Exception 
	 */
	public ArrayList<ColumnVector> nullSpace() throws Exception
	{
		//gets the upper triangular matrix
		double[] v = new double[numRows()];
		ColumnVector zero = new ColumnVector("zero", v);
		double[][] u = this.reduce(zero)[0];
		double[][] nxn = u;
		if(u.length>u[0].length)
		{
			nxn = new double[u[0].length][u[0].length];
			for(int i=0; i<u[0].length; i++)
			{
				for(int j=0; j<u[0].length; j++)
				{
					nxn[i][j] = u[i][j];
				}
			}
		}
		else if(u.length<u[0].length)
		{
			nxn = new double[u[0].length][u[0].length];
			for(int i=0; i<u.length; i++)
			{
				for(int j=0; j<u[0].length; j++)
				{
					nxn[i][j] = u[i][j];
				}
			}
		}
		u = nxn;
		//gets the number of free variables
		int[] freeVars = new int[numOfZeroRows(u)];
		int[] pivot = new int[u[0].length-freeVars.length];
		int i = 0;
		//gets the free variables
		
		for(int j=0; j<u[0].length; j++)
		{
			if(u[j][j] != 0)
			{
				pivot[i] = j;
				i++;
			}
			else
			{
				for(int k=j+1; k<u.length; k++)
				{
					if(u[j][k] != 0)
					{
						pivot[i] = k;
						i++;
						break;
					}
				}
			}
			if(i==pivot.length)
			{
				break;
			}
		}
		i =0;
		for(int j=0; j<u.length; j++)
		{
			boolean isFree = true;
			for(int k=0; k<pivot.length; k++)
			{
				if(pivot[k]==j)
				{
					isFree = false;
					break;
				}
			}
			if(isFree)
			{
				freeVars[i] = j;
				i++;
			}
			if(i==freeVars.length)
			{
				break;
			}
		}
		if(pivot.length==0)
		{
			for(i=0; i<freeVars.length; i++)
			{
				freeVars[i] = i;
			}
		}
		//creates the container of the null vectors
		ArrayList<ColumnVector> nullsp = new ArrayList<ColumnVector>();
		//gets a vector for each free variable
		for(i=0; i<freeVars.length; i++)
		{
			
			double[] vector = new double[u[0].length];
			//sets the current free variable to 1
			vector[freeVars[i]] = 1.0;
			for(int j = u.length-1; j>=0; j--)
			{
				for(int k =0; k<u[0].length; k++)
				{
					if(u[j][k] != 0)
					{
						//calculates the vector
						for(int l =k+1; l<u[0].length; l++)
						{
							boolean infrvars = false;
							for(int m=0; m<freeVars.length; m++)
							{
								if(k==freeVars[m])
								{
									infrvars = true;
								}
							}
							//the value is already known break
							if(!infrvars)
							{
								vector[k] += -vector[l]*u[j][l]/u[j][k];
							}
							
						}
						break;
					}
				}
				
			}
			nullsp.add(new ColumnVector("c"+i, vector));
		}
		return nullsp;
	}
	
	/**
	 * reduces the matrix into upper triangular form while doing the came operations on a vector
	 * @param v
	 * @return
	 * @throws Exception
	 */
	private double[][][] reduce(ColumnVector v) throws Exception
	{
		if(v.length() != numRows())
		{
			throw new Exception("The vector needs to have the same length as the number of rows.");
		}
		//creates the p l and u matrices 
		double[][] u = getMatrix();
		double[] vector = new double[v.length()];
		for(int i=0; i<v.length(); i++)
		{
			vector[i] = v.getValueAt(i);
		}
		//performing all the row operations 
		for(int i=0; i<u.length-1; i++)
		{
			int k =i;
			//while the element of the matrix is 0 then go to the next element in the matrix
			while(k<u[0].length-1 && u[i][k] == 0)
			{
				//tries to find a row that does not have 0 for the kth element
				if(u[i][k] == 0)
				{
					int j =0;
					for(j=k+1; j<u.length; j++)
					{
						if(u[j][k]!=0)
						{
							u = swapRows(u, i, j);
							double temp = vector[i];
							vector[i] = vector[j];
							vector[j] = temp;
							break;
						}
						if(j+1 == u.length)
						{
							break;
						}
					}
					
				}
				//if no row exists go to the next element
				if(u[i][k] == 0)
				{
					k++;
				}
			}
			//if not 0 then set l matrix element and subtract the jth row from the ith row
			if(u[i][k] != 0)
			{
				for(int j=0; j<u.length; j++)
				{
					if(j!=i)
					{
						vector[j] -= u[j][k]*vector[i]/u[i][k];
						u = this.subtractRows(u, i, j, u[i][k], u[j][k]);
					}	
				}
			}
			
		}
		//finds an shifts the 0 rows to the bottom of the matrix
		for(int i=0; i<u.length-1; i++)
		{
			int zeroRow = 0;
			int j =0;
			for(j=0; j<u[0].length; j++)
			{
				if(u[i][j] == 0)
				{
					zeroRow++;
				}
			}
			if(zeroRow == u[0].length)
			{
				int k =0;
				for(j=i+1; j<u.length; j++)
				{
					zeroRow = 0;
					for(k=0; k<u[0].length; k++)
					{
						if(u[j][k] == 0)
						{
							zeroRow++;
						}
					}
					if(zeroRow < u[0].length)
					{
						break;
					}
				}
				if(zeroRow<u[0].length)
				{
					u = swapRows(u, i, j);
					double temp = vector[i];
					vector[i] = vector[j];
					vector[j] = temp;
				}
				
			}
			
		}
		double[][][] retVal = new double[2][u.length][];
		retVal[0] = u;
		retVal[1][0] = vector;
		return retVal;
	}
	
	/**
	 * finds number of rows that are 0 
	 * @param m
	 * @return
	 */
	private int numOfZeroRows(double[][] m)
	{
		int count = 0;
		for(int i=0; i<m.length;i++)
		{
			int j = 0;
			for(j=0; j<m[0].length; j++)
			{
				if(m[i][j] != 0)
				{
					break;
				}
				if(j+1 == m[0].length)
				{
					j = m[0].length;
					break;
				}
			}
			if(j == m[0].length)
			{
				count++;
			}
		}
		return count;
	}
	/**
	 * Subtracts row1 multiplied and divided by a certain amount into row2 and returns resulting matrix
	 * @param row1
	 * @param row2
	 * @param divR1
	 * @param multR1
	 * @return
	 * @throws Exception
	 */
	private double[][] subtractRows(double[][] next, int row1, int row2, double divR1, double multR1) throws Exception
	{
		//checks boundaries 
		if(row1 >=0 && row2>=0 && row1<numRows() && row2<numRows())
		{
			for(int i=0; i<next[0].length; i++)
			{
				double temp = -multR1*(next[row1][i]/divR1) + next[row2][i];
				if(Double.isInfinite(temp))
				{
					throw new Exception("Value Overflow the numbers are Larger than the Calculator can Handle");
				}
				next[row2][i] = temp;
			}
			return next;
		}
		throw new Exception("Index out of bounds");
	}


	/**
	 * gets the index of the matrix
	 * @return
	 */
	public int getIndex(){return index;}
	/**
	 * sets the index of the matrix
	 * @param what
	 */
	public void setIndex(int what){this.index = what;}
	
	/**
	 * gets the tag of the matrix
	 */
	public String getTag()
	{
		return this.TAG;
	}
	/**
	 * sets the tag of the matrix
	 * @param tAG
	 */
	public void setTAG(String tAG)
	{
		TAG = tAG;
	}
	
	public String getFormattedMatrix() throws Exception
	{
		String s = "";
		for(int i = 0; i < numRows(); i++) {
			for(int j = 0; j < numCols(); j++)
			{
				if(j == numCols()-1)
				{
					s+= getValueAt(i, j);
				}
				else s += getValueAt(i,j)+"  ";
			}
			s += "\n";
		}
		return s;
	}
	
	@Override
	public String getInfo()
	{
		return ""; // I am Matrix. You need to call the result activity to view me!
	}
	
	public String toString()
	{
		return String.format("%s : %d by %d",this.getName(),
				numRows(), numCols());

	}
}